Corelab Seminar
2020-2021
Panayotis Mertikopoulos
Games, Dynamics, and Optimization
Abstract.
This talk aims to survey the triple-point interface between optimization, game theory, and dynamical systems. In the first part of the talk, we will discuss how the ordinary differential equation (ODE) method of stochastic approximation can be used to analyze the trajectories of stochastic first-order algorithms in non-convex programs – both in terms of convergence to the problem's critical set as well as the avoidance of non-minimizing critical manifolds. Subsequently, we will examine the behavior of these algorithms in a game-theoretic context involving several optimizing agents, each with their individual objective. In this multi-agent setting, the situation is considerably more involved: On the one hand, if the game being played satisfies a monotonicity condition known as "diagonal strict convexity" (Rosen, Econometrica, 1965), the induced sequence of play converges to Nash equilibrium with probability 1. On the other hand, in non-monotone games, the sequence of play may converge with arbitrarily high probability to spurious attractors that are in no way unilaterally stable (or even stationary). "Traps" of this type can arise even in simple two-player zero-sum games with one-dimensional action sets and polynomial payoffs, a fact which highlights the fundamental gap between min-min and min-max problems.